P5929 [POI1999]地图

至少有一半不小于 A(k)A(k) , 至少有一半不大于 A(k)A(k)

所以 A(k)A(k) 应该是选出的区域人口的中位数。

为了使误差尽可能小,每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »

SP4060 KPGAME - A game with probability

dp[0/1][i]dp[0/1][i] :有 ii 颗石子 Alice/Bob 为先手,Alice 赢的概率

PP 为 Alice 拿走石子的概率, QQ 为 Bob 拿走石子的概率。

{dp[0][i]=dp[1][i1]P+dp[1][i](1P)dp[1][i]=dp[0][i1]Q+dp[0][i](1Q)\begin{cases}

阅读全文 »

P1560 [USACO5.2]蜗牛的旅行

这道题是一道典型的搜索题,我们用dfs(x,y,step,s)dfs(x,y,step,s)表示蜗牛在(x,y)(x,y)这个点,走了stepstep步,当前的方向(起点的s=0s=0,特殊处理一下)。

当蜗牛确定一个方向后,我们就不断让它前进,同时记录它走过的格子,直到它遇到障碍,出界或者到达已走过的点停止。

如果蜗牛遇到障碍,我们就枚举每个方向,因为前方有障碍,后方已经走过,所以蜗牛只会向左或向右转,不需要特殊处理。

阅读全文 »

P2894 [USACO08FEB]酒店Hotel

这道题明显是线段树的板题,至于考试时因为懒标记的小问题只有20分,我也很无奈

进入正题,既然要修改查询区间内连续的一段元素,似曾相识的感觉
我们等价的把空房子看为1,住人的房子看为0。

阅读全文 »

CF39A C*++ Calculations

题意简述

给你一个含变量xx的式子,所有xx的系数为常数,定义模糊的部分按任意次序计算。如:a+++++aa+++++a既可以先算 a++a++ , 也可以先算++a++a

给你aa的初值,求算式的最大值。

阅读全文 »

P5427 [USACO19OPEN]Left Out

为了书写方便,我们将L'L'表示为0,R'R'表示为1。

现在题目转化为给你一个01矩阵,每次可将一行或一列的01反转,要求最后只有一个1或只有一个0,问能否办到。

现在,我们将第一行和第一列的元素全变为1(0也可以),这个很好办到,翻转第一行的元素就将该元素所在列翻转,列同理。

阅读全文 »

P5017 摆渡车

这道题我们先看一下数据范围:n500,m100,0ti4×106n≤500,m≤100,0≤t_i≤4×10^6

显然复杂度和n,mn,m有关,既然如此,我们考虑用tt的复杂度来解决此题吧。(此题解法不止一种)

我们用dp[i]dp[i]表示在ii时刻发车(不管是第几次),所有在ii时刻之前到达的人的等待时间之和。tot[i]tot[i]表示第ii时刻有多少人开始等车,显然有:

阅读全文 »

CF45G Prime Problem

前置知识:哥德巴赫猜想:任一大于2的偶数都可写成两个质数之和

然后,这道题就非常水了。

S=1+2+...+nS=1+2+...+n , 我们分类讨论 SS 的情况就好了。

阅读全文 »

P3232 [HNOI2013]游走

这道题边的数量最高是10000多,而点只有500,这提醒我们,我们不能直接对边求期望,而是点。

Expection[u]Expection[u]表示点uu的期望走过次数,Degree[u]Degree[u]表示点uu的度数。

那么,

阅读全文 »